import java.util.Arrays;
import java.util.Stack;

/**
 * Created by L.jp
 * Description:
 * User: 86189
 * Date: 2021-10-23
 * Time: 10:48
 */
/*
时间复杂度：O（n*logn),最坏的时候就是数组有序的情况，还是每次都要遍历数组一遍，所以最坏是O（n^2)
空间复杂度：O（logn),最坏是O（n)
稳定性:不稳定
 */
public class QuickSort {
    //找基准值
    public static int  paitition(int[]arr,int left,int right){
        //挖坑法：
        int tmp=arr[left];
        while(left<right){
            //因为前面有一个空位，所以先从后面找一个比tmp小的
            while(left<right && arr[right]>=tmp){
                right--;
            }
            arr[left]=arr[right];
            //从前面找比tmp大的
            while(left<right && arr[left]<=tmp){
                left++;
            }
            arr[right]=arr[left];
        }
        //left和right相遇
        arr[left]=tmp;
        return left;//返回基准值下标
    }
    /*
    //直接插入排序
    public static void insertSort2(int[]array,int left,int right){
        //参数判断
        if(array==null)return;
        for (int i = left+1; i <right; i++) {
            int tmp = array[i];
            int j = i - 1;
            for (; j >= 0; j--) {
                if (array[j] > tmp) {
                    array[j + 1] = array[j];
                } else {
                    break;
                }
            }
            array[j + 1] = tmp;
        }
    }*/
    //三数取中法：让第二大的元素在最前面，最小的在中间，最大的在最后面
    /*public static void medianOfThree(int[]arr,int left,int right){
        int mid=(left+right)/2;
        if(arr[mid]>arr[left]){
            int tmp=arr[mid];
            arr[mid]=arr[left];
            arr[left]=tmp;
        }
        if(arr[mid]>arr[right]){
            int tmp=arr[mid];
            arr[mid]=arr[right];
            arr[right]=tmp;
        }
        if(arr[left]>arr[left]){
            int tmp=arr[left];
            arr[left]=arr[right];
            arr[right]=tmp;
        }
    }*/
    public static void quickSort(int[]arr, int left,int right){
        if(left>=right){
            return ;
        }
        //优化1:递归到一定区间后，此时数据越来越趋于有序，可利用直接插入排序
        /*if(right-left+1<=100){//当数据个数小于100个时
            insertSort2(arr,left,right);
            return;
        }
         */
        //优化2：挖坑法找基准值之前先用三数取中法找一个基准值，也就是取首中尾三个数找一个排在中间的数作为枢纽值放到最前面
        //medianOfThree(arr,left,right);
        int pivot=paitition(arr,left, right);//左边右边的每次的left不同
        quickSort(arr,0,pivot-1);
        quickSort(arr,pivot+1, right);
    }


    //快速排序的非递归实现：
    public static void quickSortNor(int[]arr){
        Stack<Integer> stack=new Stack<>();
        int start=0;
        int end=arr.length-1;
        int pivot=paitition(arr,start,end);//先找到基准值下标
        //基准值左右两边至少有两个元素，才可以入栈
        //先入栈四个
        if(pivot>start+1){
            stack.push(start);
            stack.push(pivot-1);
        }
        if(pivot< end-1){
            stack.push(pivot+1);
            stack.push(end);
        }
        //出栈，先判断空
        while(!stack.isEmpty()){
            //每次弹出两个
             end=stack.pop();//先弹出的是后面进来的两个下标，也就是基准值右边一个和最后一个元素的下标
             start=stack.pop();
             pivot=paitition(arr,start,end);
             if(pivot>start+1){
                 stack.push(start);
                 stack.push(pivot-1);
             }
             if(pivot<end-1){
                 stack.push(pivot+1);
                 stack.push(end);
             }
             //然后循环出栈
        }
    }
    public static void main(String[] args) {
        int []arr={1,23,12,22,21,2,15,12,3,14};
        quickSort(arr,0, arr.length-1);
        System.out.println(Arrays.toString(arr));
        quickSortNor(arr);
        System.out.println(Arrays.toString(arr));
    }
}